Упорядочение хаоса

Задание логической последовательности команд, управляющей работой компьютера, - всего лишь один аспект разработки программ. Необходимо еще так организовать обрабатываемые данные, чтобы они располагались в памяти компьютера в определенном порядке. Если бы программное обеспечение не содержало средств для организации гигантских объемов данных, подлежащих хранению и обработке, то компьютеры оказались бы фактически бесполезными. В этом случае использовать компьютер было бы столь же сложно, как, например, искать нужную информацию в энциклопедии или словаре, где статьи располагаются не по алфавиту, а чисто случайным образом.

Для организации информации и упаковки ее в память компьютера программисты используют различные технические приемы. Конечно, такие методы должны также обеспечивать компьютеру возможность получить информацию обратно, когда это потре6уехся. Эти методы довольно часто описываются с помощью понятий, используемых в нашей повседневной жизни, например, таких, как магазин, очередь или список.

Списки и связанные списки

Один из способов сортировки информации в памяти компьютера основан на использовании связанных списков. В таких списках требуемый порядок расположения элемент в поддерживается с помощью ссылок, т. е. адресов, которые указывают на область памяти содержащую очередной элемент списка. Так как элементы связаны между собой при помощи ссылок, нет необходимости храни их в непрерывном блоке памяти.

Другое свойство связанных списков заключается в том, что для добавления и исключения отдельных элементов не требуется переписывать целиком весь список. Так, если в программе обработке текстов отдельные слова документа рассматриваются элементы списка, то это позволяет вставлять или убирать фрагменты текста, не нарушая порядка остальных слов.